{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Split Message Based on Limit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: splitMessage"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #根据限制分割消息"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串&nbsp;<code>message</code>&nbsp;和一个正整数&nbsp;<code>limit</code>&nbsp;。</p>\n",
    "\n",
    "<p>你需要根据 <code>limit</code>&nbsp;将&nbsp;<code>message</code> <strong>分割</strong>&nbsp;成一个或多个 <strong>部分</strong>&nbsp;。每个部分的结尾都是&nbsp;<code>\"&lt;a/b&gt;\"</code>&nbsp;，其中&nbsp;<code>\"b\"</code>&nbsp;用分割出来的总数 <b>替换</b>，&nbsp;<code>\"a\"</code>&nbsp;用当前部分所在的编号 <strong>替换</strong>&nbsp;，编号从&nbsp;<code>1</code>&nbsp;到&nbsp;<code>b</code>&nbsp;依次编号。除此以外，除了最后一部分长度 <strong>小于等于</strong>&nbsp;<code>limit</code>&nbsp;以外，其他每一部分（包括结尾部分）的长度都应该&nbsp;<strong>等于</strong>&nbsp;<code>limit</code>&nbsp;。</p>\n",
    "\n",
    "<p>你需要确保分割后的结果数组，删掉每部分的结尾并<strong>&nbsp;按顺序&nbsp;</strong>连起来后，能够得到&nbsp;<code>message</code>&nbsp;。同时，结果数组越短越好。</p>\n",
    "\n",
    "<p>请你返回<em>&nbsp;</em><code>message</code>&nbsp; 分割后得到的结果数组。如果无法按要求分割&nbsp;<code>message</code>&nbsp;，返回一个空数组。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>message = \"this is really a very awesome message\", limit = 9\n",
    "<b>输出：</b>[\"thi&lt;1/14&gt;\",\"s i&lt;2/14&gt;\",\"s r&lt;3/14&gt;\",\"eal&lt;4/14&gt;\",\"ly &lt;5/14&gt;\",\"a v&lt;6/14&gt;\",\"ery&lt;7/14&gt;\",\" aw&lt;8/14&gt;\",\"eso&lt;9/14&gt;\",\"me&lt;10/14&gt;\",\" m&lt;11/14&gt;\",\"es&lt;12/14&gt;\",\"sa&lt;13/14&gt;\",\"ge&lt;14/14&gt;\"]\n",
    "<strong>解释：</strong>\n",
    "前面 9 个部分分别从 message 中得到 3 个字符。\n",
    "接下来的 5 个部分分别从 message 中得到 2 个字符。\n",
    "这个例子中，包含最后一个部分在内，每个部分的长度都为 9 。\n",
    "可以证明没有办法分割成少于 14 个部分。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>message = \"short message\", limit = 15\n",
    "<b>输出：</b>[\"short mess&lt;1/2&gt;\",\"age&lt;2/2&gt;\"]\n",
    "<strong>解释：</strong>\n",
    "在给定限制下，字符串可以分成两个部分：\n",
    "- 第一个部分包含 10 个字符，长度为 15 。\n",
    "- 第二个部分包含 3 个字符，长度为 8 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= message.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>message</code>&nbsp;只包含小写英文字母和&nbsp;<code>' '</code>&nbsp;。</li>\n",
    "\t<li><code>1 &lt;= limit &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [split-message-based-on-limit](https://leetcode.cn/problems/split-message-based-on-limit/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [split-message-based-on-limit](https://leetcode.cn/problems/split-message-based-on-limit/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"this is really a very awesome message\"\\n9', '\"short message\"\\n15']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitMessage(self, message: str, limit: int) -> List[str]:\n",
    "        \n",
    "        cur = 1\n",
    "        k = 1\n",
    "        while len(message) + (3 + len(str(k))) * k +  cur > k * limit and 1 + 3 + len(str(k)) < limit:\n",
    "            k += 1\n",
    "            cur += len(str(k))\n",
    "\n",
    "        if 1 + 3 + len(str(k)) >= limit:\n",
    "            return []\n",
    "\n",
    "        return self.printout(message, limit, k)\n",
    "\n",
    "        \n",
    "    def printout(self, message: str, limit: int, part: int) -> List[str]:\n",
    "        res = []\n",
    "        j = 0\n",
    "        for i in range(1, part + 1):\n",
    "            suffix = f'<{i}/{part}>'\n",
    "            offset = limit - len(suffix)\n",
    "            item = message[j: j + offset] + suffix\n",
    "            res.append(item)\n",
    "            j += offset\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitMessage(self, message: str, limit: int) -> List[str]:\n",
    "        \n",
    "        digit_min = 1\n",
    "        digit_max = limit - 4\n",
    "\n",
    "        digit = None\n",
    "        for i in range(digit_min, digit_max):\n",
    "            if self.feasible(message, limit, 10 ** i - 1):\n",
    "                digit = i\n",
    "                break\n",
    "\n",
    "        if digit is None:\n",
    "            return []\n",
    "    \n",
    "        start = 10 ** (digit - 1)\n",
    "        end = 10 ** digit - 1\n",
    "\n",
    "        while start < end:\n",
    "            mid = start + (end - start) // 2\n",
    "            if self.feasible(message, limit, mid):\n",
    "                end = mid\n",
    "            else:\n",
    "                start = mid + 1\n",
    "\n",
    "        return self.printout(message, limit, start)\n",
    "\n",
    "    def feasible(self, message: str, limit: int, part: int) -> bool:\n",
    "        suffix = 4 + len(str(part))\n",
    "        if limit - suffix <= 0:\n",
    "            return False\n",
    "\n",
    "        place = limit - suffix\n",
    "        num = 9\n",
    "        total = 0\n",
    "        test = 0\n",
    "        while part > num + test:\n",
    "            total += num * place\n",
    "            test += num    \n",
    "            num *= 10\n",
    "            place -= 1\n",
    "\n",
    "        total += (part - test) * max(0, place)\n",
    "        return total >= len(message)\n",
    "        \n",
    "    def printout(self, message: str, limit: int, part: int) -> List[str]:\n",
    "        res = []\n",
    "        j = 0\n",
    "        for i in range(1, part + 1):\n",
    "            suffix = f'<{i}/{part}>'\n",
    "            offset = limit - len(suffix)\n",
    "            item = message[j: j + offset] + suffix\n",
    "            res.append(item)\n",
    "            j += offset\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitMessage(self, message: str, limit: int) -> List[str]:\n",
    "        if limit <= 5:\n",
    "            return []\n",
    "        # 1 - 9\n",
    "        def get_num():\n",
    "            n = len(message)\n",
    "            delta = limit - 5\n",
    "            res = (n - 1) // delta + 1\n",
    "            if res <= 9:         \n",
    "                return res\n",
    "            # print(n, delta, res)\n",
    "            # 10 - 99\n",
    "            if limit <= 7:\n",
    "                return []\n",
    "            n -= 9 * (delta - 1)\n",
    "            delta = limit - 7\n",
    "            res = (n - 1) // delta + 1\n",
    "            # print(res, n, delta)\n",
    "            if res <= 90:\n",
    "                return res + 9\n",
    "            # print(n, delta, res)   \n",
    "            \n",
    "            if limit <= 9:\n",
    "                return []\n",
    "            n -= 90 * (delta - 1)\n",
    "            n += 9\n",
    "            delta = limit - 9\n",
    "            res = (n - 1) // delta + 1\n",
    "            if res <= 900:\n",
    "                return res + 99\n",
    "\n",
    "            # print(n, delta, res)\n",
    "            if limit <= 11:\n",
    "                return []\n",
    "            n -= 900 * (delta - 1)\n",
    "            n += 90\n",
    "            n += 9\n",
    "            delta = limit - 11\n",
    "            res = (n - 1) // delta + 1\n",
    "            if res <= 9000:\n",
    "                return res + 999\n",
    "        tot = get_num()\n",
    "        if tot == []:\n",
    "            return []\n",
    "        res = list()\n",
    "        cnt = 1\n",
    "        j = 0\n",
    "        i = 0\n",
    "        n = len(message)\n",
    "        # print(n)\n",
    "        while i < n:\n",
    "            base = f\"<{cnt}/{tot}>\"\n",
    "            st = message[i: i + limit - len(base)]\n",
    "            res.append(f\"{st}<{cnt}/{tot}>\")\n",
    "            cnt += 1\n",
    "            i += limit - len(base)\n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitMessage(self, message: str, limit: int) -> List[str]:\n",
    "        n = len(message)\n",
    "        \n",
    "        set_len = 1\n",
    "        while set_len+4<limit:\n",
    "            base = 1\n",
    "            max_len = 0\n",
    "            for digit in range(1, min(set_len, limit-set_len-4)+1):\n",
    "                max_len += 9*base*(limit-set_len-3-digit)\n",
    "                base *= 10\n",
    "            if max_len>=n:\n",
    "                break\n",
    "            else:\n",
    "                set_len+=1\n",
    "        \n",
    "        # print(set_len)\n",
    "        \n",
    "        if set_len>=limit-4:\n",
    "            return []\n",
    "        \n",
    "        res = []\n",
    "        i = 1\n",
    "        left = 0\n",
    "        while left<n:\n",
    "            right = left + limit-3-set_len-len(str(i))\n",
    "            if right>n:\n",
    "                right=n\n",
    "            res.append(message[left:right])            \n",
    "            i+=1\n",
    "            left=right\n",
    "        \n",
    "        m = len(res)\n",
    "        for i in range(m):\n",
    "            res[i]+=\"<{}/{}>\".format(i+1,m)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitMessage(self, message: str, limit: int) -> List[str]:\n",
    "        \n",
    "        digit_min = 1\n",
    "        digit_max = limit - 4\n",
    "\n",
    "        digit = None\n",
    "        for i in range(digit_min, digit_max):\n",
    "            if self.feasible(message, limit, 10 ** i - 1):\n",
    "                digit = i\n",
    "                break\n",
    "\n",
    "        if digit is None:\n",
    "            return []\n",
    "    \n",
    "        start = 10 ** (digit - 1)\n",
    "        end = 10 ** digit - 1\n",
    "\n",
    "        while start < end:\n",
    "            mid = start + (end - start) // 2\n",
    "            if self.feasible(message, limit, mid):\n",
    "                end = mid\n",
    "            else:\n",
    "                start = mid + 1\n",
    "\n",
    "        return self.printout(message, limit, start)\n",
    "\n",
    "    def feasible(self, message: str, limit: int, part: int) -> bool:\n",
    "        suffix = 4 + len(str(part))\n",
    "        place = limit - suffix\n",
    "        num = 9\n",
    "        total = 0\n",
    "        test = 0\n",
    "        while part > num + test and place > 0:\n",
    "            total += num * place\n",
    "            test += num    \n",
    "            num *= 10\n",
    "            place -= 1\n",
    "\n",
    "        total += (part - test) * place\n",
    "        return total >= len(message)\n",
    "        \n",
    "    def printout(self, message: str, limit: int, part: int) -> List[str]:\n",
    "        res = []\n",
    "        j = 0\n",
    "        for i in range(1, part + 1):\n",
    "            suffix = f'<{i}/{part}>'\n",
    "            offset = limit - len(suffix)\n",
    "            item = message[j: j + offset] + suffix\n",
    "            res.append(item)\n",
    "            j += offset\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "  def splitMessage(self, message: str, limit: int) -> List[str]:\n",
    "      def calc(k):\n",
    "          m = 2*k+3\n",
    "          r = 0\n",
    "          for t in range(1,k):\n",
    "              r += 10**(k-t-1) * t\n",
    "          r *= 9\n",
    "          return m,r\n",
    "\n",
    "      def get_k(n):\n",
    "          k = 0\n",
    "          while n:\n",
    "              k += 1\n",
    "              n /= 10\n",
    "          return k\n",
    "\n",
    "      l = len(message)\n",
    "      \n",
    "      ans = []\n",
    "      \n",
    "      for k in range(1,get_k(l) +1):\n",
    "          m,r = calc(k)\n",
    "          print(m,r)\n",
    "          if limit <= m: break\n",
    "          s = l - r \n",
    "          print(s)\n",
    "          start = ceil(s/(limit-m))\n",
    "          end = (s+limit)/(limit-m)\n",
    "          if start < end and start < 10**k and start>= 10**(k-1):\n",
    "              n = start\n",
    "              ptr = 0\n",
    "              for i in range(n):\n",
    "                  tail = f'<{i+1}/{n}>'\n",
    "                  pre = limit - len(tail)\n",
    "                  ans.append(message[ptr:ptr+pre]+tail)\n",
    "                  ptr += pre\n",
    "              break\n",
    "\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitMessage(self, message: str, limit: int) -> List[str]:\n",
    "        n = len(message)\n",
    "        s, l = 0, 1\n",
    "        while (x := limit - (2*l+3)) > 0:\n",
    "            y = 9 * 10**(l-1)\n",
    "            if x * y < n:\n",
    "                n -= x * y\n",
    "                s += y\n",
    "                n += s\n",
    "            else:\n",
    "                b = 10**(l-1) + (n + x-1)//x - 1\n",
    "                n = 0\n",
    "                break\n",
    "            l += 1\n",
    "        \n",
    "        if n > 0:\n",
    "            return []\n",
    "        \n",
    "        res = []\n",
    "        i, n = 0, len(message)\n",
    "        for a in range(1, b+1):\n",
    "            suffix = f'<{a}/{b}>'\n",
    "            p = limit - len(suffix)\n",
    "            res.append(message[i:i+p] + suffix)\n",
    "            i += p\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitMessage(self, message: str, limit: int) -> List[str]:\n",
    "        n = len(message)\n",
    "        def cal(k):\n",
    "       \n",
    "            tmp = k\n",
    "            cnt = 0\n",
    "            while tmp:\n",
    "                cnt += 1\n",
    "                tmp //= 10\n",
    "            need = []\n",
    "            for i in range(1,cnt):\n",
    "                if i == 1:\n",
    "                    need.append([9,4 + cnt])\n",
    "                else:\n",
    "                   \n",
    "                    need.append([pow(10,i) - pow(10,i - 1),i + 3 + cnt])\n",
    "            left = k - pow(10,cnt - 1)\n",
    "            need.append([left + 1,cnt + 3 + cnt])\n",
    "            return need\n",
    "        id = -1\n",
    "        \n",
    "        # O(nloglimit)\n",
    "        for i in range(1,n + 1):\n",
    "            # 结尾需要的长度\n",
    "            tmp = cal(i)\n",
    "            l = 0\n",
    "            f = 1\n",
    "            for j in range(len(tmp) - 1):\n",
    "                if tmp[j][1] > limit:\n",
    "                    f = 0\n",
    "                    break\n",
    "                else:\n",
    "                    need = (limit - tmp[j][1]) * tmp[j][0]\n",
    "                    if l + need >= n:\n",
    "                        f = 0\n",
    "                        break\n",
    "                    l += need\n",
    "                  \n",
    "            if tmp[-1][0] == 1:\n",
    "                if n - l + tmp[-1][1] > limit or tmp[-1][1] > limit:\n",
    "                    f = 0\n",
    "            else:\n",
    "                need = (limit - tmp[-1][1]) * (tmp[-1][0] - 1)\n",
    "                if l + need >= n:\n",
    "                    \n",
    "                    f = 0\n",
    "                l += need\n",
    "                \n",
    "                if n - l + tmp[-1][1] > limit:\n",
    "                    f = 0\n",
    "            \n",
    "            if f:\n",
    "                id = i\n",
    "                break\n",
    "        if id == -1:\n",
    "            return []\n",
    "        else:\n",
    "            l = 0\n",
    "            ans = []\n",
    "            cur = 1\n",
    "            ll = len(str(id))\n",
    "            while l < n:\n",
    "                t = len(str(cur)) + ll + 3\n",
    "                need = limit - t\n",
    "                ans.append(message[l:l + need] + '<' + str(cur) + '/' + str(id) + '>')\n",
    "                cur += 1\n",
    "                l += need\n",
    "            return ans\n",
    "            \n",
    "        \n",
    "            \n",
    "            \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitMessage(self, message: str, limit: int) -> List[str]:\n",
    "        def calc(k):\n",
    "            m = 2*k+3\n",
    "            r = 0\n",
    "            for t in range(1,k):\n",
    "                r += 10**(k-t-1) * t\n",
    "            r *= 9\n",
    "            return m,r\n",
    "        l = len(message)\n",
    "        \n",
    "        ans = []\n",
    "        \n",
    "        for k in range(1,5):\n",
    "            m,r = calc(k)\n",
    "            print(m,r)\n",
    "            if limit <= m: break\n",
    "            s = l - r \n",
    "            print(s)\n",
    "            start = ceil(s/(limit-m))\n",
    "            end = (s+limit)/(limit-m)\n",
    "            if start < end and start < 10**k and start>= 10**(k-1):\n",
    "                n = start\n",
    "                ptr = 0\n",
    "                for i in range(n):\n",
    "                    tail = f'<{i+1}/{n}>'\n",
    "                    pre = limit - len(tail)\n",
    "                    ans.append(message[ptr:ptr+pre]+tail)\n",
    "                    ptr += pre\n",
    "                break\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitMessage(self, message: str, limit: int) -> List[str]:\n",
    "        i = cap = 0\n",
    "        while True:\n",
    "            i += 1\n",
    "            if i < 10:\n",
    "                tail_len = 5  # 结尾的长度\n",
    "            elif i < 100:\n",
    "                if i == 10: cap -= 9  # 前面的结尾的长度都 +1，那么容量就要减小\n",
    "                tail_len = 7\n",
    "            elif i < 1000:\n",
    "                if i == 100: cap -= 99\n",
    "                tail_len = 9\n",
    "            else:\n",
    "                if i == 1000: cap -= 999\n",
    "                tail_len = 11\n",
    "            if tail_len >= limit: return []  # cap 无法增大，寄\n",
    "            cap += limit - tail_len\n",
    "            if cap < len(message): continue  # 容量没有达到，继续枚举\n",
    "\n",
    "            ans, k = [], 0\n",
    "            for j in range(1, i + 1):\n",
    "                tail = f\"<{j}/{i}>\"\n",
    "                if j == i:\n",
    "                    ans.append(message[k:] + tail)\n",
    "                else:\n",
    "                    m = limit - len(tail)\n",
    "                    ans.append(message[k: k + m] + tail)\n",
    "                    k += m\n",
    "            return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def check(self,mid: int,limit: int,N: int) -> bool:\n",
    "        a = 0\n",
    "        t = mid\n",
    "        \n",
    "        while t>0:\n",
    "            a += 1\n",
    "            t//=10\n",
    "        \n",
    "        base = limit - 3 - a\n",
    "        if base<=0: \n",
    "            return False\n",
    "\n",
    "        cnt = mid\n",
    "        r = 1\n",
    "        b = 0\n",
    "        tot = 0\n",
    "        while cnt > 0:\n",
    "            b += 1\n",
    "            if cnt>9*r:\n",
    "                tot += (base-b)*9*r\n",
    "            else:\n",
    "                tot += (base-b)*(cnt-1)\n",
    "                if tot>=N:\n",
    "                    return False\n",
    "                elif N-tot<=base-b:\n",
    "                    return True    \n",
    "            cnt -= 9*r\n",
    "            r*=10\n",
    "\n",
    "        return False\n",
    "    def make_list(self,groupNum: int,limit: int,N: int,message: str)->List[str]:\n",
    "        l = []\n",
    "\n",
    "        a = 0\n",
    "        t = groupNum\n",
    "        while t>0:\n",
    "            a += 1\n",
    "            t//=10\n",
    "        base = limit - 3 - a\n",
    "\n",
    "        cnt = groupNum\n",
    "        r = 1\n",
    "        b = 0\n",
    "        tot = 0\n",
    "\n",
    "        left = 0\n",
    "        while cnt > 0:\n",
    "            b += 1\n",
    "            if cnt>9*r:\n",
    "                tot += (base-b)*9*r\n",
    "                for z in range(r,10*r):\n",
    "                    l.append(message[left:left+base-b]+'<'+str(z)+'/'+str(groupNum)+'>')\n",
    "                    left += base-b\n",
    "\n",
    "            else:\n",
    "                \n",
    "\n",
    "                for z in range(r,groupNum+1):\n",
    "                    l.append(message[left:left+base-b]+'<'+str(z)+'/'+str(groupNum)+'>')\n",
    "                    left += base-b\n",
    "                \n",
    "            cnt -= 9*r\n",
    "            r*=10\n",
    "        return l\n",
    "    def splitMessage(self, message: str, limit: int) -> List[str]:\n",
    "        N = len(message)\n",
    "        \n",
    "        \n",
    "\n",
    "        for i in range(1,N+1):\n",
    "            \n",
    "            if self.check(i,limit,N):\n",
    "                return self.make_list(i,limit,N,message)\n",
    "\n",
    "        return[]\n",
    "        \n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitMessage(self, message: str, limit: int) -> List[str]:\n",
    "        \n",
    "        digit_min = 1\n",
    "        digit_max = limit - 4\n",
    "\n",
    "        digit = None\n",
    "        for i in range(digit_min, digit_max):\n",
    "            if self.feasible(message, limit, 10 ** i - 1):\n",
    "                digit = i\n",
    "                break\n",
    "\n",
    "        if digit is None:\n",
    "            return []\n",
    "    \n",
    "        start = 10 ** (digit - 1)\n",
    "        end = 10 ** digit - 1\n",
    "\n",
    "        while start < end:\n",
    "            mid = start + (end - start) // 2\n",
    "            if self.feasible(message, limit, mid):\n",
    "                end = mid\n",
    "            else:\n",
    "                start = mid + 1\n",
    "\n",
    "        return self.printout(message, limit, start)\n",
    "\n",
    "    def feasible(self, message: str, limit: int, part: int) -> bool:\n",
    "        suffix = 4 + len(str(part))\n",
    "        if limit - suffix <= 0:\n",
    "            return False\n",
    "\n",
    "        place = limit - suffix\n",
    "        num = 9\n",
    "        total = 0\n",
    "        test = 0\n",
    "        while part > num + test:\n",
    "            total += num * place\n",
    "            test += num    \n",
    "            num *= 10\n",
    "            place -= 1\n",
    "\n",
    "        total += (part - test) * place\n",
    "        return total >= len(message)\n",
    "        \n",
    "    def printout(self, message: str, limit: int, part: int) -> List[str]:\n",
    "        res = []\n",
    "        j = 0\n",
    "        for i in range(1, part + 1):\n",
    "            suffix = f'<{i}/{part}>'\n",
    "            offset = limit - len(suffix)\n",
    "            item = message[j: j + offset] + suffix\n",
    "            res.append(item)\n",
    "            j += offset\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitMessage(self, message: str, limit: int) -> List[str]:\n",
    "        n, cap = 0, 0  # 可分割的个数和容量　\n",
    "        l = len(message)\n",
    "        while 1:\n",
    "            n += 1\n",
    "            if n < 10:\n",
    "                # <a/b>\n",
    "                tail_len = 5\n",
    "            elif n < 100:\n",
    "                if n == 10: cap -= 9  # 前面九个的结尾  1/9   9/9   的长度都 +1，那么容量就要减小\n",
    "                tail_len = 7\n",
    "            elif n < 1000:\n",
    "                if n == 100: cap -= 99\n",
    "                tail_len = 9\n",
    "            else:\n",
    "                if n == 1000: cap -= 999\n",
    "                tail_len = 11\n",
    "            \n",
    "            if limit - tail_len <= 0: return []\n",
    "            cap += limit - tail_len\n",
    "            if cap < l: continue\n",
    "            \n",
    "            ans = []\n",
    "            k = 0\n",
    "            for j in range(1, n + 1):\n",
    "                tail = f'<{j}/{n}>'\n",
    "                if j < n:\n",
    "                    cur = limit - len(tail)\n",
    "                    ans.append(message[k:k + cur] + tail)\n",
    "                    k += cur\n",
    "                else:\n",
    "                    ans.append(message[k:] + tail)\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitMessage(self, message: str, limit: int) -> List[str]:\n",
    "        N = len(message)\n",
    "        if limit <= 5: return []\n",
    "        if (N + limit -6 ) // (limit - 5) <= 9:\n",
    "            limit -= 5\n",
    "            parts = (N+limit-1)//limit\n",
    "            return [message[off:off+limit] + f\"<{off//limit + 1}/{parts}>\" for off in range(0, N, limit)]\n",
    "        for base in range(2, (limit -1)//2+1):\n",
    "            s = sum((limit - 4 - base - t)*9*10**t for t in range(base-1))\n",
    "            if N <= s + (limit - 3-base*2)*9*10**(base-1):\n",
    "                break\n",
    "        else:\n",
    "            return []\n",
    "        parts = (N - s + limit - 4 - base*2) // (limit-3-base*2) + 10**(base-1) - 1\n",
    "        res = [None]*parts\n",
    "        level, stride = 10, limit - 3 - base - 1\n",
    "        off = 0\n",
    "        for part in range(1, parts+1):\n",
    "            if part == level:\n",
    "                level *= 10\n",
    "                stride -= 1\n",
    "            res[part-1] = message[off:off+stride] + f\"<{part}/{parts}>\"\n",
    "            off += stride\n",
    "        return res\n",
    "        # (3+n+1)*9 + (3+n+2)*90+(3+n+3)*900+(3+n+n)*(n-10000)+r\n",
    "        # n*9+4*9+n*90+5*90+n*900+6*900 ...+ n*2*(10**n)\n",
    "\n",
    "        # >(l - 4 - n)*9+(l-5-n)*90+(l-6-n)*900+...(l-3-n-n+1)*9*(10**(n-2))\n",
    "        # <=\n",
    "\n",
    "        # l - 4 - n > 0\n",
    "        # l - 3 - n - n > 0\n",
    "        # 2n < l - 3 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitMessage(self, message: str, limit: int) -> List[str]:\n",
    "        \n",
    "        digit_min = 1\n",
    "        digit_max = limit - 4\n",
    "\n",
    "        digit = None\n",
    "        for i in range(digit_min, digit_max):\n",
    "            if self.feasible(message, limit, 10 ** i - 1):\n",
    "                digit = i\n",
    "                break\n",
    "\n",
    "        if digit is None:\n",
    "            return []\n",
    "    \n",
    "        start = 10 ** (digit - 1)\n",
    "        end = 10 ** digit - 1\n",
    "\n",
    "        while start < end:\n",
    "            mid = start + (end - start) // 2\n",
    "            if self.feasible(message, limit, mid):\n",
    "                end = mid\n",
    "            else:\n",
    "                start = mid + 1\n",
    "\n",
    "        return self.printout(message, limit, start)\n",
    "\n",
    "    def feasible(self, message: str, limit: int, part: int) -> bool:\n",
    "        suffix = 4 + len(str(part))\n",
    "        if limit - suffix <= 0:\n",
    "            return False\n",
    "\n",
    "        place = limit - suffix\n",
    "        num = 9\n",
    "        total = 0\n",
    "        test = 0\n",
    "        while part > num + test:\n",
    "            total += num * place\n",
    "            test += num    \n",
    "            num *= 10\n",
    "            place -= 1\n",
    "\n",
    "        total += (part - test) * max(0, place)\n",
    "        return total >= len(message)\n",
    "        \n",
    "    def printout(self, message: str, limit: int, part: int) -> List[str]:\n",
    "        res = []\n",
    "        j = 0\n",
    "        for i in range(1, part + 1):\n",
    "            suffix = f'<{i}/{part}>'\n",
    "            offset = limit - len(suffix)\n",
    "            item = message[j: j + offset] + suffix\n",
    "            res.append(item)\n",
    "            j += offset\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitMessage(self, message:str, limit: int) -> List[str]:\n",
    "        i = cap = 0\n",
    "        while True:\n",
    "            i += 1\n",
    "            if i < 10:\n",
    "                tail_len = 5\n",
    "            elif i < 100:\n",
    "                if i == 10:\n",
    "                    cap -= 9\n",
    "                tail_len = 7\n",
    "            elif i < 1000:\n",
    "                if i == 100:\n",
    "                    cap -= 99\n",
    "                tail_len = 9\n",
    "            else:\n",
    "                if i == 1000:\n",
    "                    cap -= 999\n",
    "                tail_len = 11\n",
    "            if tail_len >= limit:\n",
    "                return []\n",
    "            cap += limit - tail_len\n",
    "            if cap < len(message):\n",
    "                continue\n",
    "            \n",
    "            ans, k = [], 0\n",
    "            for j in range(1, i + 1):\n",
    "                tail = f'<{j}/{i}>'\n",
    "                if j == i:\n",
    "                    ans.append(message[k:] + tail)\n",
    "                else:\n",
    "                    m = limit - len(tail)\n",
    "                    ans.append(message[k:k+m] + tail)\n",
    "                    k += m\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def solve(message, limit, n):\n",
    "    res = []\n",
    "    pos = 0\n",
    "    for i in range(n):\n",
    "        cur = \"<\" + str(i+1) + \"/\" + str(n) + \">\"\n",
    "        left = limit - len(cur)\n",
    "        res.append(message[pos: pos + left] + cur)\n",
    "        pos += left\n",
    "    return res\n",
    "\n",
    "class Solution:\n",
    "    def splitMessage(self, message: str, limit: int) -> List[str]:\n",
    "        n = len(message)\n",
    "        # 按位数去BS\n",
    "        cur_need = 3\n",
    "        digit = 1\n",
    "        def test(mid, n, digit):\n",
    "            nonlocal limit, cur_need\n",
    "            TEST_mid = mid\n",
    "            s =  mid * limit - cur_need * mid - mid * digit\n",
    "            tmp_sum = 0\n",
    "            for i in range(1, len(str(mid))+ 1):\n",
    "                cur_size = pow(10, i) - tmp_sum\n",
    "                tmp_sum += cur_size\n",
    "                if i == 1:\n",
    "                    cur_size = 9\n",
    "                cur_size = min(cur_size, mid)\n",
    "                mid -= cur_size\n",
    "                s -= cur_size * i\n",
    "            print(\"test: \", TEST_mid, \"s: \", s)\n",
    "            if s >= n:\n",
    "                return True\n",
    "        def BS(l, h, n, digit):\n",
    "            tmp = True\n",
    "            while l < h:\n",
    "                mid = l + (h-l)//2\n",
    "                tmp = test(mid, n, digit)\n",
    "                if tmp:\n",
    "                    h = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            return l\n",
    "        while cur_need + digit * 2<= limit:\n",
    "            l,h = pow(10, digit - 1), pow(10, digit)-1\n",
    "            res = BS(l, h, n, digit)\n",
    "            if test(res, n, digit):\n",
    "                return solve(message, limit, res)\n",
    "            digit += 1\n",
    "        return []\n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitMessage(self, message: str, limit: int) -> List[str]:\n",
    "        n = len(message)\n",
    "        base = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            x = i\n",
    "            while x:\n",
    "                base[i] += 1 \n",
    "                x //= 10 \n",
    "        for i in range(1, n + 1):\n",
    "            start = 1 \n",
    "            tol = 0\n",
    "            while start < i:\n",
    "                curLen = limit - 3 - base[start] - base[i]\n",
    "                tol += (min(i, start * 10) - start) * curLen\n",
    "                start *= 10 \n",
    "            if tol < n and n - tol + 3 + base[i] + base[i] <= limit:\n",
    "                break \n",
    "        else:\n",
    "            return []\n",
    "        res = []\n",
    "        pre = 0\n",
    "        x = i\n",
    "        for i in range(1, x + 1):\n",
    "            curLen = limit - 3 - base[i] - base[x]\n",
    "            res.append(message[pre : pre + curLen] + '<' + str(i) + '/' + str(x) + '>')\n",
    "            pre += curLen\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitMessage(self, message: str, limit: int) -> List[str]:\n",
    "        i = cap = 0\n",
    "        while True:\n",
    "            i += 1\n",
    "            if i < 10:\n",
    "                tail_len = 5\n",
    "            elif i < 100:\n",
    "                if i == 10:\n",
    "                    cap -= 9\n",
    "                tail_len = 7\n",
    "            elif i < 1000:\n",
    "                if i == 100:\n",
    "                    cap -= 99\n",
    "                tail_len = 9\n",
    "            else:\n",
    "                if i == 1000:\n",
    "                    cap -= 999\n",
    "                tail_len = 11\n",
    "            if tail_len >= limit: \n",
    "                return []\n",
    "            cap += limit - tail_len\n",
    "            if cap < len(message):\n",
    "                continue\n",
    "            \n",
    "            ans, k = [], 0\n",
    "            for j in range(1, i+1):\n",
    "                tail = f'<{j}/{i}>'\n",
    "                if j == i:\n",
    "                    ans.append(message[k:] + tail)\n",
    "                else:\n",
    "                    m = limit - len(tail)\n",
    "                    ans.append(message[k:k+m] + tail)\n",
    "                    k += m\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitMessage(self, message: str, limit: int) -> List[str]:\n",
    "        n = len(message)\n",
    "\n",
    "        def getMessages(l):\n",
    "            idx = 0\n",
    "            count = 0\n",
    "            res = []\n",
    "            while count < n:\n",
    "                idx += 1\n",
    "                add = min(limit - (1 + len(str(idx)) + 1 + l + 1), n - count)\n",
    "                res.append(message[count:count+add] + '<' + str(idx) + '/')\n",
    "                count += add\n",
    "            for i in range(len(res)):\n",
    "                res[i] = res[i] + str(idx) + '>'\n",
    "            return res\n",
    "\n",
    "        \n",
    "        for i in range(1, limit):\n",
    "            if i * 2 + 3 >= limit:\n",
    "                break\n",
    "            cost = (1 + 1 + i + 1) * ((10**i) - 1)\n",
    "            for j in range(1, i+1):\n",
    "                cost += ((10**j - 1) - (10**(j-1) - 1)) * j\n",
    "            if (10**i - 1) * limit - cost >= n:\n",
    "                return getMessages(i) \n",
    "        \n",
    "        return []\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# 1: xxx<1/9>,xxx<2/9>,xxx<3/9> ... ... xxx<7/9>,xxx<8/9>,xxx<9/9>\n",
    "# 2: xxx<1/99>,xxx<2/99>...xxx<10/99>,xxx<11/99>...xxx<98/99>,xxx<99/99>\n",
    "# 3: xxx<1/999>,xxx<2/999>...xxx<10/999>,xxx<11/999>...xxx<998/999>,xxx<999/999>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitMessage(self, message: str, limit: int) -> List[str]:\n",
    "        n = len(message)\n",
    "        base = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            x = i\n",
    "            while x:\n",
    "                base[i] += 1 \n",
    "                x //= 10 \n",
    "        for i in range(1, n + 1):\n",
    "            start = 1 \n",
    "            tol = 0\n",
    "            while start < i:\n",
    "                curLen = limit - 3 - base[start] - base[i]\n",
    "                tol += (min(i, start * 10) - start) * curLen\n",
    "                start *= 10 \n",
    "            if tol < n and n - tol + 3 + base[i] + base[i] <= limit:\n",
    "                break \n",
    "        else:\n",
    "            return []\n",
    "        res = []\n",
    "        pre = 0\n",
    "        x = i\n",
    "        for i in range(1, x + 1):\n",
    "            curLen = limit - 3 - base[i] - base[x]\n",
    "            res.append(message[pre : pre + curLen] + '<' + str(i) + '/' + str(x) + '>')\n",
    "            pre += curLen\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitMessage(self, message: str, limit: int) -> List[str]:\n",
    "        n = len(message)\n",
    "        f = [0] * (n + 1)\n",
    "        for i in range(1,n + 1):\n",
    "            j = i\n",
    "            while j:\n",
    "                f[i] += 1\n",
    "                j //= 10\n",
    "        print(f)\n",
    "\n",
    "        def genearate(start,length,which,all):\n",
    "            return message[start:start+length] + \"<\" + str(which) + \"/\" + str(all) + \">\"\n",
    "\n",
    "        for x in range(1,n+1):\n",
    "            total = 0\n",
    "            i,j = 1,10\n",
    "            while i < x:\n",
    "                each = limit - 3 - f[x] - f[i]\n",
    "                total += each * (min(j,x) - i)\n",
    "                i *= 10\n",
    "                j *= 10\n",
    "            if n - total > 0 and n - total <= limit - 3 - f[x] * 2:\n",
    "                res = []\n",
    "                start = 0\n",
    "                for i in range(1,x):\n",
    "                    each = limit - 3 - f[x] - f[i]\n",
    "                    res.append(genearate(start,each,i,x))\n",
    "                    start += each\n",
    "                res.append(genearate(start,n - start,x,x))\n",
    "                return res\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitMessage(self, message: str, limit: int) -> List[str]:\n",
    "        i = cap = 0\n",
    "        while True:\n",
    "            i += 1\n",
    "            if i < 10:\n",
    "                tail_len = 5  # 结尾的长度\n",
    "            elif i < 100:                \n",
    "                if i == 10: cap -= 9  # 前面的结尾的长度都 +1，那么容量就要减小\n",
    "                tail_len = 7\n",
    "            elif i < 1000:\n",
    "                if i == 100: cap -= 99\n",
    "                tail_len = 9\n",
    "            else:\n",
    "                if i == 1000: cap -= 999\n",
    "                tail_len = 11\n",
    "            if tail_len >= limit: return []  # cap 无法增大，寄\n",
    "            cap += limit - tail_len\n",
    "            if cap < len(message): continue  # 容量没有达到，继续枚举\n",
    "            ans, k = [], 0\n",
    "            for j in range(1, i + 1):\n",
    "                tail = f\"<{j}/{i}>\"\n",
    "                if j == i:\n",
    "                    ans.append(message[k:] + tail)\n",
    "                else:\n",
    "                    m = limit - len(tail)\n",
    "                    ans.append(message[k: k + m] + tail)\n",
    "                    k += m\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitMessage(self, message: str, limit: int) -> List[str]:\n",
    "        n = len(message)\n",
    "        base = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            x = i\n",
    "            while x:\n",
    "                base[i] += 1 \n",
    "                x //= 10 \n",
    "        for i in range(1, n + 1):\n",
    "            start = 1 \n",
    "            tol = 0\n",
    "            while start < i:\n",
    "                curLen = limit - 3 - base[start] - base[i]\n",
    "                tol += (min(i, start * 10) - start) * curLen\n",
    "                start *= 10 \n",
    "            if tol < n and n - tol + 3 + base[i] + base[i] <= limit:\n",
    "                break \n",
    "        else:\n",
    "            return []\n",
    "        res = []\n",
    "        pre = 0\n",
    "        x = i\n",
    "        for i in range(1, x + 1):\n",
    "            curLen = limit - 3 - base[i] - base[x]\n",
    "            res.append(message[pre : pre + curLen] + '<' + str(i) + '/' + str(x) + '>')\n",
    "            pre += curLen\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitMessage(self, message: str, limit: int) -> List[str]:\n",
    "        n = len(message)\n",
    "        base = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            x = i\n",
    "            while x:\n",
    "                base[i] += 1 \n",
    "                x //= 10 \n",
    "        # print(base)\n",
    "        for i in range(1, n + 1):\n",
    "            start = 1 \n",
    "            tol = 0\n",
    "            while start < i:\n",
    "                curLen = limit - 3 - base[start] - base[i]\n",
    "                tol += (min(start * 10, i) - start) * curLen\n",
    "                start *= 10 \n",
    "            if tol < n and n - tol + 3 + base[i] + base[i] <= limit:\n",
    "                break \n",
    "        else:\n",
    "            return []\n",
    "        res = []\n",
    "        pre = 0\n",
    "        x = i\n",
    "        for i in range(1, x + 1):\n",
    "            curLen = limit - 3 - base[i] - base[x]\n",
    "            res.append(message[pre : pre + curLen] + '<' + str(i) + '/' + str(x) + '>')\n",
    "            pre += curLen\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def splitMessage(self, message: str, limit: int) -> List[str]:\n",
    "        n = len(message)\n",
    "        base = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            x = i \n",
    "            while x:\n",
    "                base[i] += 1 \n",
    "                x //= 10 \n",
    "        for i in range(1, n + 1):\n",
    "            tol = 0\n",
    "            start = 1 \n",
    "            while start < i:\n",
    "                curLen = limit - 3 - base[start] - base[i]\n",
    "                tol += (min(start * 10, i) - start) * curLen\n",
    "                start *= 10 \n",
    "            if tol < n and n - tol + 3 + base[i] + base[i] <= limit:\n",
    "                break \n",
    "        else:\n",
    "            return []\n",
    "        res = []\n",
    "        x = i\n",
    "        pre = 0\n",
    "        for i in range(1, x + 1):\n",
    "            curLen = limit - 3 - base[i] - base[x]\n",
    "            res.append(message[pre : pre + curLen] + '<' + str(i) + '/' + str(x) + '>')\n",
    "            pre = pre + curLen\n",
    "        return res \n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
